#include <stdio.h>

#include <stdlib.h>
typedef struct LNode
{
  int val;               // 节点值
  struct LNode *next; // 指向下一节点的指针
} LNode;

// 辅助函数：创建新节点
LNode *createNode(int val)
{
  LNode *newNode = (LNode *)malloc(sizeof(LNode));
  newNode->val = val;
  newNode->next = NULL;
  return newNode;
}

// 辅助函数：构建测试链表（示例：1->2->3->4->5）
LNode *buildList()
{
  LNode *head = createNode(1);
  head->next = createNode(2);
  head->next->next = createNode(3);
  head->next->next->next = createNode(4);
  head->next->next->next->next = createNode(5);
  return head;
}

LNode *findKthFromEnd(LNode *head, int k)
{
  // 处理非法情况：k≤0 或 链表为空
  if (k <= 0 || head == NULL)
  {
    return NULL;
  }

  LNode *fast = head; // 快指针
  LNode *slow = head; // 慢指针

  // 快指针先移动 k 步
  for (int i = 0; i < k; i++)
  {
    // 若快指针提前到末尾，说明 k 超过链表长度
    if (fast == NULL)
    {
      return NULL;
    }
    fast = fast->next;
  }

  // 快慢指针同时移动，直到快指针到末尾
  while (fast != NULL)
  {
    fast = fast->next;
    slow = slow->next;
  }

  return slow; // 慢指针指向倒数第 k 个节点
}

// 辅助函数：打印链表
void printList(LNode *head)
{
  LNode *cur = head;
  while (cur != NULL)
  {
    printf("%d -> ", cur->val);
    cur = cur->next;
  }
  printf("NULL\n");
}

int main()
{
  // 1. 构建测试链表
  LNode *head = buildList();
  printf("Original list: ");
  printList(head);

  // 2. 查找倒数第 k 个节点（示例：k=2）
  int k = 2;
  LNode *kthNode = findKthFromEnd(head, k);

  // 3. 输出结果
  if (kthNode != NULL)
  {
    printf("The %d-th node from the end is: %d\n", k, kthNode->val);
  }
  else
  {
    printf("Invalid k or list is empty.\n");
  }

  // 4. 释放链表内存（防止内存泄漏）
  LNode *cur = head;
  while (cur != NULL)
  {
    LNode *temp = cur;
    cur = cur->next;
    free(temp);
  }

  return 0;
}